The full execution of Bubble Sort demonstrates how the largest unsorted element "bubbles up" to its final position in each pass.

  • The previous slide successfully demonstrated that after the first pass ($i=0$), the largest element (8) is correctly positioned. We now continue the trace for the remaining passes, observing how the sorted suffix gradually consumes the array $A$.
  • For an array of size $n=5$, Bubble Sort requires $n-1=4$ total passes (indexed $i=0$ to $i=3$) to guarantee sorting.
  • In each subsequent pass $i$, the inner comparison loop automatically reduces its bounds, executing $n-1-i$ comparisons. This reduction is key, as it avoids processing the elements already placed into the final sorted suffix.
  • The full process demonstrates why the algorithm's worst-case time complexity is $O(n^2)$, as the sum of comparisons across all passes is $(n-1) + (n-2) + \dots + 1$.
Pass Index (i) # Comparisons Resulting Array State $A$
Initial State N/A [8, 2, 5, 1, 6]
i=0 4 [2, 5, 1, 6, 8]
i=1 3 [2, 1, 5, 6, 8]
i=2 2 [1, 2, 5, 6, 8]
i=3 1 [1, 2, 5, 6, 8]
Python Implementation: bubble_sort
1def bubble_sort(A):
2    n = len(A)
3    # Outer loop determines the passes (i)
4    for i in range(n - 1):
5        # Inner loop handles comparisons (j), reduced by i
6        for j in range(n - 1 - i):
7            # Comparison (Comparison_Color)
8            if A[j] > A[j+1]:
9                # Swap (Swap_Animation)
10                A[j], A[j+1] = A[j+1], A[j]
11    return A